#![allow(dead_code)]
use crate::compr::random_array;
use std::fmt::Display;

pub struct List {
    head: Link,
}
type Link = Option<Box<Node>>;

#[derive(Debug)]
struct Node {
    elem: i32,
    next: Link,
}
impl Node {
    fn new(elem: i32) -> Self {
        Self { elem, next: None }
    }
}

impl Display for List {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "链表：")?;
        if self.head.is_none() {
            write!(f, "None")?;
            return Ok(());
        }
        let mut next = self.head.as_ref();

        while let Some(node) = next {
            write!(f, "{} -> ", node.elem)?;
            next = node.next.as_ref();
        }
        write!(f, "None")?;

        Ok(())
    }
}

impl List {
    fn new() -> Self {
        Self { head: None }
    }

    fn push(&mut self, elem: i32) -> &mut Self {
        if self.head.is_none() {
            self.head = Some(Box::new(Node::new(elem)));
            return self;
        }

        let mut pnode = self.head.as_mut();
        while let Some(cur_node) = pnode {
            if cur_node.next.is_none() {
                pnode = Some(cur_node);
                break;
            }
            pnode = cur_node.next.as_mut();
        }
        pnode.map(|node| node.next = Some(Box::new(Node::new(elem))));

        self
    }

    fn reverse(&mut self) {
        let mut rnode: Link = self.head.take();
        let mut lnode: Link = None;

        while let Some(mut node) = rnode {
            rnode = node.next;
            node.next = lnode;
            lnode = Some(node);
        }
        self.head = lnode;
    }

    /* 栈 */
    fn is_palindrome1(&self) -> bool {
        if self.head.is_none() {
            return true;
        }

        let mut cur = self.head.as_ref();
        let mut v = vec![];
        while let Some(node) = cur {
            v.push(node.elem);
            cur = node.next.as_ref();
        }

        cur = self.head.as_ref();
        while let Some(elem) = v.pop() {
            let node = cur.unwrap();
            if node.elem != elem {
                return false;
            }
            cur = node.next.as_ref();
        }
        true
    }

    fn middle_node(&self) -> Option<&Box<Node>> {
        if self.head.is_none() {
            return None;
        }

        let mut fast = self.head.as_ref();
        let mut slow = self.head.as_ref();

        while fast.is_some() && fast.unwrap().next.is_some() {
            slow = slow.unwrap().next.as_ref();
            fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
        }
        slow
    }
}

pub fn test_list() {
    let mut list = List::new();
    let arr = random_array(10, 0..101);
    for num in arr {
        list.push(num);
    }
    println!("{}", list);
    println!("中间结点：{:?}", list.middle_node());
    list.reverse();
    println!("反转链表：{}", list);
    println!("是否是回文：{}", list.is_palindrome1());
    println!("中间结点：{:?}", list.middle_node());

    let arr = vec![1, 2, 3, 4, 5, 4, 3, 2, 1];
    let mut list = List::new();
    for num in arr {
        list.push(num);
    }
    println!("{}", list);
    println!("是否是回文：{}", list.is_palindrome1());
    println!("中间结点：{:?}", list.middle_node());
}
